//回溯算法框架：解决一个回溯问题，实际上就是一个决策树遍历的过程，只需思考三个问题：

// 1. 路径：也就是已经做出的选择；
// 2. 选择列表：也就是当前你可以做的选择；
// 3. 结束条件：也就是到达决策树底层，无法再做选择的条件。

// 代码框架：

result = [];

def backtrack(路径， 选择列表):
	if 满足结束条件:
		result.add(路径)
		return

	for 选择 in 选择列表
		做选择
		backtrack(路径，选择列表)
		撤销选择

// --------------------------------------------------------------

// 回溯算法框架：解决一个回溯问题，实际上就是一个决策树遍历的过程，只需要思考三个问题：

// 1. 路径：也就是已经做出的选择；
// 2. 选择列表：也就是当前你可以做的选择；
// 3. 结束条件：也就是到达决策树底层，无法再做选择的条件

// 代码框架：

result = [];

def backtrack(路径，选择列表)
	if 满足结束条件：
		result.add(路径)
		return

	for 选择 in 选择列表
		做选择
		backtrack(路径， 选择列表)
		撤销选择


// --------------------------------------------------------------------

// 回溯算法框架：解决一个回溯问题，实际上就是一个决策树遍历的过程，只需要思考三个问题：

// 1. 路径：也就是已经做出的选择；
// 2. 选择列表：也就是当前你可以做的选择；
// 3. 结束条件：也就是到达决策树底层，无法再做选择的条件

// 代码框架：

result = [];

def backtrack(路径，选择列表)
	if 满足结束条件
		result.add(路径)
		return

	for 选择 in 选择列表
		做选择
		backtrack(路径， 选择列表)
		撤销选择


class Solution {
public:

    vector<vector<int>> res; // 记录结果

    vector<vector<int>> permute(vector<int>& nums) 
    {
        int n = nums.size();

        vector<int> track; // 记录路径 - 已经做出的选择
        vector<bool> used(n, false); // 可认为是选择列表 - 记录路径中的元素(已经使用过，就不能在选择列表中出现了)

        backtrack(nums, track, used);

        return res;
    }

    void backtrack(vector<int>& nums, vector<int>& track, vector<bool>& used)
    {
        // base case - 路径的长度 == 数组的大小
        if(track.size() == nums.size())
        {
            res.push_back(track);
            return;
        }

        for(int i = 0; i < nums.size(); i++)
        {
            if(used[i])
                continue;

            track.push_back(nums[i]);
            used[i] = true;

            backtrack(nums, track, used);

            track.pop_back();
            used[i] = false;

            // res.push_back(track);
        }

    }
};


class Solution {
public:

    vector<vector<int>> res;

    vector<vector<int>> permute(vector<int>& nums) 
    {
        int n = nums.size();

        vector<int> track;
        vector<int> used(n, false);

        backtrack(nums, track, used);

        return res;
    }

    void backtrack(vector<int>& nums, vector<int>& track, vector<int>& used)
    {
        // base case - 结束的条件
        if(track.size() == nums.size())
        {
            res.push_back(track);
            return;
        }

        for(int i = 0; i < nums.size(); i++)
        {
            if(used[i])
                continue;

            // 做选择
            track.push_back(nums[i]);
            used[i] = true;

            backtrack(nums, track, used);

            // 撤销选择
            track.pop_back();
            used[i] = false;
        }
    }
};


class Solution {
public:

    vector<vector<string>> res;

    vector<vector<string>> solveNQueens(int n) 
    {
        // '.'表示空，'Q'表示放置皇后，初始化为空棋盘
        vector<string> board(n, string(n, '.'));

        backtrack(board, 0);

        return res;
    }

    // 路径：board中小于row的那些行都已经成功放置了皇后
    // 选择列表：第row行中所有列都是放置皇后的选择
    // 结束条件：当row超过了board的最后一行
    void backtrack(vector<string>& board, int row)
    {
        // 结束条件
        if(board.size() == row)
        {
            res.push_back(board);
            return;
        }

        int n = board[row].size();
        for(int col = 0; col < n; col++)
        {
            // 排除不合法的选择
            if(!valid(board, row, col))
                continue;

            // 做选择
            board[row][col] = 'Q';

            // 进行下一次决策
            backtrack(board, row + 1);

            // 撤销选择
            board[row][col] = '.';
        }
    }

    // 是否可以在board[row][col]位置放置皇后？
    bool valid(vector<string>& board, int row, int col)
    {
        int n = board.size();

        // 检查列是否有皇后相互冲突？
        for(int i = 0; i <= row; i++)
        {
            if(board[i][col] == 'Q')
                return false;
        }

        // 检查右上方是否有皇后冲突？
        for(int i = row-1, j = col+1; i >= 0 && j < n; i--, j++)
        {
            if(board[i][j] == 'Q')
                return false;
        }

        // 检查左上方是否有皇后冲突？
        for(int i = row-1, j=col-1; i >= 0 && j >= 0; i--, j--)
        {
            if(board[i][j] == 'Q')
                return false;
        }

        return true;
    }
};


class Solution {
public:

    vector<vector<string>> res;

    vector<vector<string>> solveNQueens(int n) 
    {
        // 'Q'表示放置了皇后，'.'表示空，初始化棋盘为空
        vector<string> board(n, string(n, '.'));

        backtrack(board, 0);

        return res;
    }

    // 路径：棋盘中的第row行之前都已经放置了皇后
    // 选择列表：第row行的所有列都是放置皇后的选择
    // 结束条件：row到了棋盘的最后一行
    void backtrack(vector<string>& board, int row)
    {
        if(row == board.size())
        {
            res.push_back(board);
            return;
        }

        int n = board[row].size();

        for(int col = 0; col < n; col++)
        {
            // 当前位置不符合条件
            if(!valid(board, row, col))
                continue;

            // 做选择
            board[row][col] = 'Q';

            backtrack(board, row+1);

            // 撤销选择
            board[row][col] = '.';
        }
    }

    // 判断board[row][col]位置是否满足题目要求
    bool valid(vector<string>& board, int row, int col)
    {
        int n = board.size();

        // 判断所在的列是否满足放置皇后的要求
        for(int i = 0; i <= row; i++)
        {
            if(board[i][col] == 'Q')
                return false;
        }

        // 判断右上角是否满足放置皇后的要求
        for(int i = row-1, j = col+1; i >= 0 && j < n; i--, j++)
        {
            if(board[i][j] == 'Q')
                return false;
        }

        // 判断左上角是否满足放置皇后的要求
        for(int i = row-1, j=col-1; i >= 0 && j >= 0; i--, j--)
        {
            if(board[i][j] == 'Q')
                return false;
        }

        return true;
    }
};



class Solution {
public:

    int res = 0;

    int totalNQueens(int n) 
    {
        // 'Q'表示放置了皇后，'.'表示为空，初始化棋盘为空
        vector<string> board(n, string(n, '.'));

        backtrack(board, 0);

        return res;
    }

    void backtrack(vector<string>& board, int row)
    {
        // 结束条件 - row到了棋盘的最后一行
        if(row == board.size())
        {
            res++;
            return;
        }

        int n = board[row].size();
        for(int col = 0; col < n; col++)
        {
            // 判断board[row][col]位置是否满足条件
            if(!isValid(board, row, col))
                continue;

            // 做选择
            board[row][col] = 'Q';

            backtrack(board, row + 1);

            // 撤销选择
            board[row][col] = '.';
        }
    }

    bool isValid(vector<string>& board, int row, int col)
    {
        int n = board.size();

        // 判断列是否满足条件
        for(int i = 0; i <= row; i++)
        {   
            if(board[i][col] == 'Q')
                return false;
        }

        // 判断右上角是否满足条件
        for(int i=row-1, j=col+1; i >= 0 && j < n; i--, j++)
        {
            if(board[i][j] == 'Q')
                return false;
        }

        // 判断左上角是否满足条件
        for(int i=row-1, j=col-1; i >= 0 && j >= 0; i--, j--)
        {
            if(board[i][j] == 'Q')
                return false;
        }

        return true;
    }
};


class Solution {
public:

    vector<vector<int>> res;

    vector<int> track; // 记录回溯递归路径上的值

    vector<vector<int>> subsets(vector<int>& nums) 
    {   
        backtrack(nums, 0);

        return res;
    }

    void backtrack(vector<int>& nums, int start)
    {
        res.push_back(track);

        for(int i = start; i < nums.size(); i++)
        {
            // 做选择
            track.push_back(nums[i]);

            backtrack(nums, i + 1);

            // 撤销选择
            track.pop_back();
        }
    }
};


class Solution {
public:

    vector<vector<int>> res;

    vector<int> track; //记录回溯递归路径

    vector<vector<int>> combine(int n, int k) 
    {
        backtrack(1, n, k); // start必须从1开始，不是数组，是数字1开始

        return res;
    }

    void backtrack(int start, int n, int k) 
    {
        // 结束条件
        if(k == track.size())
        {
            res.push_back(track);
            return;
        }

        for(int i = start; i <= n; i++)
        {
            // 做选择
            track.push_back(i);

            backtrack(i + 1, n, k);

            // 撤销选择
            track.pop_back();
        }
    }
};


class Solution {
public:

    vector<vector<int>> res;

    vector<int> track; // 记录回溯递归路径

    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());

        backtrack(nums, 0);

        return res;
    }

    void backtrack(vector<int>& nums, int start)
    {
        res.push_back(track);

        for(int i = start; i < nums.size(); i++)
        {
            if(i > start && nums[i] == nums[i-1]) // 剪枝
                continue; 

            track.push_back(nums[i]);

            backtrack(nums, i + 1);

            track.pop_back();
        }
    }
};

class Solution {
public:

    vector<vector<int>> res;

    vector<int> track; // 记录回溯递归路径
    int trackSum = 0; // 记录回溯路径和

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
    {
        sort(candidates.begin(), candidates.end());

        backtrack(candidates, 0, target);

        return res;
    }

    void backtrack(vector<int>& candidates, int start, int target)
    {
        // 结束条件
        if(trackSum == target)
        {
            res.push_back(track);
            return;
        }
         if(trackSum > target)
                return;


        for(int i = start; i < candidates.size(); i++)
        {
            if(i > start && candidates[i] == candidates[i-1])
                continue;

            // 做选择
            track.push_back(candidates[i]);
            trackSum += candidates[i];

            backtrack(candidates, i + 1, target);

            // 撤销选择
            track.pop_back();
            trackSum -= candidates[i];
        }
    }

};


class Solution {
public:

    vector<vector<int>> res;

    vector<int> track; // 记录回溯递归路径

    vector<bool> used; // 记录回溯递归路径上的值是否被使用

    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());

        int n = nums.size();

        used = vector<bool>(n, false);

        backtrack(nums);

        return res;
    }

    void backtrack(vector<int>& nums)
    {
        if(track.size() == nums.size())
        {
            res.push_back(track);
            return;
        }

        for(int i = 0; i < nums.size(); i++)
        {
            if(used[i])
                continue;
            if(i > 0 && nums[i] == nums[i-1] && !used[i-1])
                continue;

            track.push_back(nums[i]);
            used[i] = true;

            backtrack(nums);

            track.pop_back();
            used[i] = false;
        }
    }
};

class Solution {
public:

    vector<vector<int>> res;

    vector<int> track; // 记录回溯递归路径

    vector<bool> used; // 记录回溯递归路径节点是否被使用

    vector<vector<int>> permute(vector<int>& nums) 
    {
        int n = nums.size();

        used = vector<bool>(n, false);

        backtrack(nums);

        return res;
    }
    
    // 路径：回溯递归路径上符合条件的元素
    // 选择列表：除去nums数组中已经在路径中的元素 - used[i]=false
    // 结束条件：路径长度=数组大小
    void backtrack(vector<int>& nums)
    {
        if(track.size() == nums.size())
        {
            res.push_back(track);
            return;
        }

        for(int i = 0; i < nums.size(); i++)
        {
            if(used[i])
                continue;

            // 做选择
            track.push_back(nums[i]);
            used[i] = true;

            backtrack(nums);

            // 撤销选择
            track.pop_back();
            used[i] = false;
        }
    }

};

class Solution {
public:

    vector<vector<int>> res;

    vector<int> track;

    vector<bool> used;

    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());

        used = vector<bool>(nums.size(), false);

        backtrack(nums);

        return res;
    }

    void backtrack(vector<int>& nums)
    {
        if(track.size() == nums.size())
        {
            res.push_back(track);
            return;
        }

        for(int i = 0; i < nums.size(); i++)
        {
            if(used[i])
                continue;
            if(i > 0 && nums[i] == nums[i-1] && !used[i-1])
                continue;

            // 做选择
            track.push_back(nums[i]);
            used[i] = true;

            backtrack(nums);

            // 撤销选择
            track.pop_back();
            used[i] = false;
        }
    }
};


class Solution {
public:

    vector<vector<int>> res;

    vector<int> track; // 记录回溯递归路径

    int trackSum = 0; // 记录回溯递归路径上的元素和

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        backtrack(candidates, 0, target);

        return res;
    }

    void backtrack(vector<int>& candidates, int start, int target)
    {
        if(trackSum == target)
        {
            res.push_back(track);
            return;
        }

        if(trackSum > target)
            return;

        for(int i = start; i < candidates.size(); i++)
        {
            // 做选择
            track.push_back(candidates[i]);
            trackSum += candidates[i];

            backtrack(candidates, i, target);

            // 撤销选择
            track.pop_back();
            trackSum -= candidates[i];
        }
    }
};


// class Solution {
// public:

//     vector<vector<int>> res;

//     vector<int> track;

//     int trackSum = 0;

//     vector<vector<int>> combinationSum3(int k, int n) 
//     {
//         backtrack(1, k, n);

//         return res;
//     }

//     void backtrack(int start, int k, int n)
//     {
//         if(k == track.size())
//         {
//             if(trackSum == n)
//             {
//                 res.push_back(track);
//                 return;
//             }
//         }

//         if(trackSum > n)
//             return;

//         if(track.size() > k)
//             return;

//         for(int i = start; i <= n; i++)
//         {
//             // 做选择
//             track.push_back(i);
//             trackSum += i;

//             backtrack(i+1, k, n);

//             // 撤销选择
//             track.pop_back();
//             trackSum -= i;
//         }
//     }
// };


class Solution {

vector<vector<int>> res;
vector<int> track;
int trackSum = 0;

public:
    vector<vector<int>> combinationSum3(int k, int n) 
    {
        backtrack(n, k, 1);
        return res;
    }

    void backtrack(int n, int k, int start)
    // void backtrack(int n, int k, int start, int curSum)
    {
        if(track.size() == k && trackSum == n)
        {
            res.push_back(track);
            return;
        }

        if(trackSum > n)
            return;

        for(int i = start; i <= 9; i++)
        {
            track.push_back(i);
            trackSum += i;
            backtrack(n, k, i+1);
            track.pop_back();
            trackSum -= i;
        }
    }
};


class Solution {
public:

    vector<vector<int>> res;

    vector<int> track;

    int trackSum = 0;

    vector<vector<int>> combinationSum3(int k, int n) 
    {
        backtrack(n, k, 1);

        return res;
    }

    void backtrack(int n, int k, int start)
    {
        // 结束条件
        if(track.size() == k && n == trackSum)
        {
            res.push_back(track);
            return;
        }

        if(trackSum > n)
            return;

        for(int i = start; i <= 9; i++)
        {
            track.push_back(i);
            trackSum += i;

            backtrack(n, k, i + 1);

            track.pop_back();
            trackSum -= i;
        }
    }
};


class Solution {
public:

    vector<vector<int>> res;

    vector<int> track;

    vector<vector<int>> subsets(vector<int>& nums) 
    {
        backtrack(nums, 0);

        return res;
    }

    void backtrack(vector<int>& nums, int start)
    {
        // 结束条件
        res.push_back(track);

        for(int i = start; i < nums.size(); i++)
        {
            track.push_back(nums[i]);

            backtrack(nums, i + 1);

            track.pop_back();
        }
    }
};

class Solution {
public:

    vector<vector<int>> res;

    vector<int> track;

    vector<vector<int>> combine(int n, int k) 
    {
        backtrack(n, k, 1);

        return res;
    }

    void backtrack(int n, int k, int start)
    {
        // 结束条件
        if(track.size() == k)
        {
            res.push_back(track);
            return;
        }

        for(int i = start; i <= n; i++)
        {
            track.push_back(i);

            backtrack(n, k, i + 1);

            track.pop_back();
        }
    }
};


class Solution {
public:

    vector<vector<int>> res;

    vector<int> track;

    int trackSum = 0;

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        backtrack(candidates, target, 0);

        return res;
    }

    void backtrack(vector<int>& candidates, int target, int start)
    {
        // 结束条件
        if(trackSum == target)
        {
            res.push_back(track);
            return;
        }

        if(trackSum > target)
            return;

        for(int i = start; i < candidates.size(); i++)
        {
            track.push_back(candidates[i]);
            trackSum += candidates[i];

            backtrack(candidates, target, i);

            track.pop_back();
            trackSum -= candidates[i];
        }
    }
};

class Solution {
public:

    vector<vector<int>> res;

    vector<int> track;

    int trackSum = 0;

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
    {
        // 有重 - 不可复选 - 组合
        sort(candidates.begin(), candidates.end());

        backtrack(candidates, target, 0);

        return res;
    }

    void backtrack(vector<int>& candidates, int target, int start)
    {
        // 结束条件
        if(trackSum == target)
        {
            res.push_back(track);
            return;
        }
        if(trackSum > target)
            return;

        for(int i = start; i < candidates.size(); i++)
        {
            if(i > start && candidates[i] == candidates[i-1])
                continue;

            track.push_back(candidates[i]);
            trackSum += candidates[i];

            backtrack(candidates, target, i + 1);

            track.pop_back();
            trackSum -= candidates[i];

        }
    }
};


class Solution {
public:

    vector<vector<int>> res;

    vector<int> track;

    vector<bool> used;

    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        // 重复元素 - 不可复选 - 排列
        sort(nums.begin(), nums.end());

        used = vector<bool>(nums.size(), false);

        backtrack(nums);

        return res;
    }

    void backtrack(vector<int>& nums)
    {
        // 结束条件
        if(track.size() == nums.size())
        {
            res.push_back(track);
            return;
        }

        for(int i = 0; i < nums.size(); i++)
        {
            if(used[i])
                continue;

            if(i > 0 && nums[i] == nums[i-1] && !used[i-1])
                continue;

            // 做选择
            track.push_back(nums[i]);
            used[i] = true;

            backtrack(nums);

            // 不做选择
            track.pop_back();
            used[i] = false;
        }
    }
};


class Solution {
public:
    int numIslands(vector<vector<char>>& grid) 
    {
        int res = 0;

        int m =  grid.size(), n = grid[0].size();

        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == '1')
                {
                    res++;

                    dfs(grid, i, j); // 将其周围岛屿淹了
                }
            }
        }      

        return res;
    }

    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        int m = grid.size(), n = grid[0].size();

        if(i < 0 || i >= m || j < 0 || j >= n)
            return;

        // 已经是海水了，返回
        if(grid[i][j] == '0')
            return;

        // 将(i,j)变成海水
        grid[i][j] = '0';
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
};

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) 
    {
        // 封闭岛屿数量=岛屿数量-靠上靠下靠左靠右岛屿数
        int m = grid.size(), n = grid[0].size();

        for(int i = 0; i < n; i++)
        {
            // 靠上岛屿淹了
            dfs(grid, 0, i);

            // 靠下岛屿淹了
            dfs(grid, m-1, i);
        }

        for(int i = 0; i < m; i++)
        {
            // 靠左岛屿淹了
            dfs(grid, i, 0);

            // 靠右岛屿淹了
            dfs(grid, i, n-1);
        }

        // 遍历矩阵，求封闭岛屿数量
        int res = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == 0)
                {
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    void dfs(vector<vector<int>>& grid, int i, int j)
    {
        int m = grid.size(), n = grid[0].size();

        if(i < 0 || i >= m || j < 0 || j >= n)
            return;

        if(grid[i][j] == 1)
            return; // 本身就是海水

        // 将(i,j)位置淹了
        grid[i][j] = 1;

        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
};


class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) 
    {
        // 封闭岛屿的数量=岛屿的数量-靠上靠下靠左靠右的岛屿数量
        int m = grid.size(), n = grid[0].size();

        for(int i = 0; i < n; i++)
        {
            // 靠上岛屿淹了
            dfs(grid, 0, i);

            // 靠下岛屿淹了
            dfs(grid, m - 1, i); // PS
        }

        for(int i = 0; i < m; i++)
        {
            // 靠左岛屿淹了
            dfs(grid, i, 0);

            // 靠右岛屿淹了
            dfs(grid, i, n - 1); // PS
        }

        int res = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == 0)
                {
                    res++;
                    dfs(grid, i, j);
                }
            }
        }

        return res;
    }

    void dfs(vector<vector<int>>& grid, int i, int j)
    {
        int m = grid.size(), n = grid[0].size();

        if(i < 0 || j < 0 || i >= m || j >= n)
            return;

        // 已经是海水了
        if(grid[i][j] == 1)
            return;

        // 将其变成海水
        grid[i][j] = 1;

        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
};


class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) 
    {
        int m = grid.size(), n = grid[0].size();

        for(int i = 0; i < n; i++)
        {
            // 靠上岛屿淹了
            dfs(grid, 0, i);

            // 靠下岛屿淹了
            dfs(grid, m - 1, i);
        }

        for(int i = 0; i < m; i++)
        {
            // 靠左岛屿淹了
            dfs(grid, i, 0);

            // 靠右岛屿淹了
            dfs(grid, i, n - 1);
        }

        int res = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == 1)
                    res++;
            }
        }

        return res;
    }

    void dfs(vector<vector<int>>& grid, int i, int j)
    {
        int m = grid.size(), n = grid[0].size();

        if(i < 0 || j < 0 || i >= m || j >= n)
            return;

        if(grid[i][j] == 0)
            return;

        grid[i][j] = 0;

        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
};

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) 
    {
        int res = 0; // 记录岛屿的最大面积

        int m = grid.size(), n = grid[0].size();

        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == 1)
                {
                    res = max(res, dfs(grid, i, j));
                }
            }
        }

        return res;
    }

    int dfs(vector<vector<int>>& grid, int i, int j)
    {
        int m = grid.size(), n = grid[0].size();

        if(i < 0 || j < 0 || i >= m || j >= n)
            return 0;

        if(grid[i][j] == 0)
            return 0;

        grid[i][j] = 0;

        return dfs(grid, i - 1, j) + 
               dfs(grid, i + 1, j) +
               dfs(grid, i, j - 1) +
               dfs(grid, i, j + 1) + 1;

    }
};


class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) 
    {
        int m = grid1.size(), n = grid1[0].size();

        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid1[i][j] == 0 && grid2[i][j] == 1)
                {
                    // 不符合题意子岛屿，淹掉
                    dfs(grid2, i, j);
                }
            }
        }

        // 现在grid2剩余的岛屿都是子岛屿，统计个数
        int res = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid2[i][j] == 1)
                {
                    res++;
                    dfs(grid2, i, j);
                }
            }
        }

        return res;
    }

    void dfs(vector<vector<int>>& grid2, int i, int j)
    {
        int m = grid2.size(), n  = grid2[0].size();

        if(i < 0 || j < 0 || i >= m || j >= n)
            return;

        if(grid2[i][j] == 0)
            return;

        grid2[i][j] = 0;

        dfs(grid2, i - 1, j);
        dfs(grid2, i + 1, j);
        dfs(grid2, i, j - 1);
        dfs(grid2, i, j + 1);
    }
};

class Solution {
public:
    // int numDistinctIslands(vector<vector<int>>& grid) 
    // {
    //     int m = grid.size(), n = grid[0].size();
    //     // 记录所有岛屿的序列化结果
    //     unordered_set<string> islands;
    //     for (int i = 0; i < m; i++) 
    //     {
    //         for (int j = 0; j < n; j++) 
    //         {
    //             if (grid[i][j] == 1) 
    //             {
    //                 // 淹掉这个岛屿，同时存储岛屿的序列化结果
    //                 string curIsland = "";
    //                 // 初始的方向可以随便写，不影响正确性
    //                 dfs(grid, i, j, curIsland, 666);
    //                 islands.insert(curIsland);

    //             }
    //         }
    //     }
    //     // 不相同的岛屿数量
    //     return islands.size();
    // }

    // void dfs(vector<vector<int>>& grid, int i, int j, string& sb, int dir) 
    // {
    //     int m = grid.size(), n = grid[0].size();
    //     if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0)
    //         return;
    //     // 前序遍历位置：进入 (i, j)
    //     grid[i][j] = 0;
    //     sb += to_string(dir) + ',';
        
    //     dfs(grid, i - 1, j, sb, 1); // 上
    //     dfs(grid, i + 1, j, sb, 2); // 下
    //     dfs(grid, i, j - 1, sb, 3); // 左
    //     dfs(grid, i, j + 1, sb, 4); // 右
        
    //     // 后序遍历位置：离开 (i, j)
    //     sb += to_string(-dir) + ',';
    // }

    int numDistinctIslands(vector<vector<int>>& grid) 
    {
        int m = grid.size(), n = grid[0].size();

        // 记录序列化结果
        unordered_set<string> islands;

        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == 1)
                {
                    // 淹掉这个岛屿，同时存储岛屿的序列化结果
                    string str = "";
                    // 初始化随便写，不影响结果
                    dfs(grid, i, j, str, 666);

                    islands.insert(str);
                }
            }
        }

        return islands.size();
    }

    void dfs(vector<vector<int>>& grid, int i, int j, string& str, int obj)
    {
        int m = grid.size(), n = grid[0].size();

        if(i < 0 || j < 0 || i >= m || j >= n)
            return;

        if(grid[i][j] == 0)
            return;

        grid[i][j] = 0;

        str += to_string(obj) + ",";

        dfs(grid, i - 1, j, str, 1); // 上
        dfs(grid, i + 1, j, str, 2); // 下
        dfs(grid, i, j - 1, str, 3); // 左
        dfs(grid, i, j + 1, str, 4); // 右

        str += to_string(-obj) + ",";
    }

};


class Solution {
public:

    vector<string> res;

    string track;

    vector<string> generateParenthesis(int n) 
    {
        backtrack(n, n);

        return res;
    }

    // 可用的左括号为left个，可用的右括号为right个
    void backtrack(int left, int right)
    {
        // 结束条件
        if(right < left) // 若左括号剩下的多，肯定不合法
            return;
        if(left < 0 || right < 0)
            return;

        if(left == 0 && right == 0)
        {
            res.push_back(track);
            return;
        }

        // 做选择，加入左括号
        track.push_back('(');
        backtrack(left - 1, right);
        // 撤销选择
        track.pop_back();

        // 做选择，加入右括号
        track.push_back(')');
        backtrack(left, right - 1);
        //撤销选择
        track.pop_back();
    }
};


class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) 
    {
        int res = 0; //记录岛屿的最大面积

        int m = grid.size(), n = grid[0].size();

        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == 1)
                {
                    // 淹没岛屿，并更新最大岛屿面积
                    res = max(res, dfs(grid, i, j));
                }
            }
        }

        return res;
    }

    int dfs(vector<vector<int>>& grid, int i, int j)
    {
        int m = grid.size(), n = grid[0].size();

        if(i < 0 || j < 0 || i >= m || j >= n)
            return 0;

        if(grid[i][j] == 0)
            return 0;

        grid[i][j] = 0;

        return dfs(grid, i - 1, j) + 
               dfs(grid, i + 1, j) + 
               dfs(grid, i, j - 1) + 
               dfs(grid, i, j + 1) + 1;
    }
};

class Solution {
public:

    // 记录结果
    vector<vector<int>> res;

    // 记录递归回溯路径
    vector<int> track;

    // 记录回溯路径是否被遍历
    vector<bool> used;

    vector<vector<int>> permute(vector<int>& nums) 
    {
        int n = nums.size();

        used.resize(n, false);

        traverse(nums);

        return res;
    }

    void traverse(vector<int>& nums)
    {
        // 结束条件
        if(track.size() == nums.size())
        {
            res.push_back(track);
            return;
        }

        for(int i = 0; i < nums.size(); i++)
        {
            if(used[i])
            continue;

            // 做选择
            track.push_back(nums[i]);
            used[i] = true;

            traverse(nums);

            // 撤销选择
            track.pop_back();
            used[i] = false;
        }
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    vector<vector<int>> res;

    // 记录回溯递归路径
    vector<int> path;

    vector<vector<int>> pathSum(TreeNode* root, int target) 
    {   
        if(root == nullptr)
            return res;

        traverse(root, target);

        return res;
    }

    void traverse(TreeNode* root, int target)
    {
        if(root == nullptr)
            return;

        int num = target - root->val;

        if(root->left == nullptr && root->right == nullptr)
        {
            if(num == 0)
            {
                path.push_back(root->val);
                res.push_back(path);
                path.pop_back();
            }
            
            return;
        }

        // 做选择 - 撤销选择
        path.push_back(root->val);
        traverse(root->left, num);
        path.pop_back();

        // 做选择 - 撤销选择
        path.push_back(root->val);
        traverse(root->right, num);
        path.pop_back();
    }
};


class Solution {
public:

    // 记录结果
    vector<string> res;

    // 记录回溯递归路径
    string track;

    vector<string> generateParenthesis(int n) 
    {
        if(n == 0)
            return {};

        traverse(n, n); // 一开始左右括号个数初始化成n个

        return res;
    }

    // 左右括号的剩余数量
    void traverse(int left, int right)
    {
        // 左括号剩的多
        if(left > right)
            return;

        // 若左括号或者右括号还有剩余
        if(left < 0 || right < 0)
            return;

        if(left == 0 && right == 0)
        {
            res.push_back(track);
            return;
        }

        // 做选择 - 撤销选择
        track.push_back('(');
        traverse(left - 1, right);
        track.pop_back();

        // 做选择 - 撤销选择
        track.push_back(')');
        traverse(left, right - 1);
        track.pop_back();
    }
};


class Solution {
public:

    // 记录结果
    vector<string> res;

    // 记录回溯递归路径
    string track;

    vector<string> generateParenthesis(int n) 
    {
        if(n == 0)
            return {};

        traverse(n, n); // 一开始左右括号个数初始化成n个

        return res;
    }

    // 左右括号的剩余数量
    void traverse(int left, int right)
    {
        // 左括号剩的多
        if(left > right)
            return;

        // 若左括号或者右括号还有剩余
        if(left < 0 || right < 0)
            return;

        if(left == 0 && right == 0)
        {
            res.push_back(track);
            return;
        }

        // 做选择 - 撤销选择
        track.push_back('(');
        traverse(left - 1, right);
        track.pop_back();

        // 做选择 - 撤销选择
        track.push_back(')');
        traverse(left, right - 1);
        track.pop_back();
    }
};


vector<string> res; // 记录结果

deque<string> track; // 使用双端队列记录链表

vector<string> restoreIpAddresses(string s)
{
	backtrack(s, 0);

	return res;
}

void backtrack(string& s, int start)
{	
	// 递归出口是track为4层(s被分成了合法的4部分)
	if(start == s.size() && track.size() == 4)
	{
		res.push_back(join_track(track));
		return;
	}

	for(int i = 0; i < start; i++)
	{
		if(!isTrueIp(s, start, i))
			continue;

		if(track.size() >= 4)
			break;

		track.push_back(s.substr(start, i - start + 1));

		backtrack(s, i + 1);

		track.pop_back();
	}
}

string join_track(deque<string> track)
{	
	string res = "";

	for(int i = 0; i < track.size(); i++)
	{
		res += track[i];
		if(i < track.size() - 1)
			res += '.';
	}

	return res;
}

bool isTreeIp(string s, int start, int end)
{
	int len = end - start + 1;

	if(len > 3 || len == 0) // 长度不合要求
		return false;

	if(len > 1 && s[start] == '0') // 不合要求
		return false;

	if(stoi(s.substr(start, len)) > 255)
		return false;

	return true;
}



